package leetcode101.complex_datastructure;

/**
 * @author Synhard
 * @version 1.0
 * @class Code7
 * @description 351. 安卓系统手势解锁
 * 我们都知道安卓有个手势解锁的界面，是一个 3 x 3 的点所绘制出来的网格。用户可以设置一个 “解锁模式” ，
 * 通过连接特定序列中的点，形成一系列彼此连接的线段，每个线段的端点都是序列中两个连续的点。
 * 如果满足以下两个条件，则 k 点序列是有效的解锁模式：
 *
 * 解锁模式中的所有点 互不相同 。
 * 假如模式中两个连续点的线段需要经过其他点，那么要经过的点必须事先出现在序列中（已经经过），不能跨过任何还未被经过的点。
 *  
 *
 * 以下是一些有效和无效解锁模式的示例：
 *
 *
 *
 *  
 * 无效手势：[4,1,3,6] ，连接点 1 和点 3 时经过了未被连接过的 2 号点。
 * 无效手势：[4,1,9,2] ，连接点 1 和点 9 时经过了未被连接过的 5 号点。
 * 有效手势：[2,4,1,3,6] ，连接点 1 和点 3 是有效的，因为虽然它经过了点 2 ，但是点 2 在该手势中之前已经被连过了。
 * 有效手势：[6,5,4,1,9,2] ，连接点 1 和点 9 是有效的，因为虽然它经过了按键 5 ，但是点 5 在该手势中之前已经被连过了。
 * 给你两个整数，分别为 m 和 n ，那么请你统计一下有多少种 不同且有效的解锁模式 ，是 至少 需要经过 m 个点，但是 不超过 n 个点的。
 *
 * 两个解锁模式 不同 需满足：经过的点不同或者经过点的顺序不同。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：m = 1, n = 1
 * 输出：9
 * 示例 2：
 *
 * 输入：m = 1, n = 2
 * 输出：65
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-07-04 9:13
 */
public class Code3 {

    private static int res;
    private static DSU dsu;

    public static void main(String[] args) {

    }

    public int numberOfPatterns(int m, int n) {
        res = 0;
        boolean[] visited = new boolean[10];
        dsu = new DSU(10);
        dsu.union(1, 3);
        dsu.union(1, 7);
        dsu.union(1, 9);
        dsu.union(2, 8);
        dsu.union(4, 6);
        for (int i = 1; i < 10; i++) {
            dfs(i, 1, visited, m, n);
        }
        return res;
    }

    private void dfs(int curKey, int keyNum, boolean[] visited, int m, int n) {
        if (keyNum > m) {
            return;
        }
        if (keyNum >= n && keyNum <= m) {
            res++;
        }
        visited[curKey] = true;
        for (int i = 1; i < 10; i++) {
            boolean mid = dsu.connected(curKey, i);
            if (!visited[i] && (!mid || visited[(curKey + i) >> 1])) {
                dfs(i, keyNum + 1, visited, m, n);
            }
        }
        visited[curKey] = false;
    }

}
